{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Group Shifted Strings"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: groupStrings"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #移位字符串分组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个字符串，对该字符串可以进行 &ldquo;移位&rdquo; 的操作，也就是将字符串中每个字母都变为其在字母表中后续的字母，比如：<code>&quot;abc&quot; -&gt; &quot;bcd&quot;</code>。这样，我们可以持续进行 &ldquo;移位&rdquo; 操作，从而生成如下移位序列：</p>\n",
    "\n",
    "<pre>&quot;abc&quot; -&gt; &quot;bcd&quot; -&gt; ... -&gt; &quot;xyz&quot;</pre>\n",
    "\n",
    "<p>给定一个包含仅小写字母字符串的列表，将该列表中所有满足&nbsp;&ldquo;移位&rdquo; 操作规律的组合进行分组并返回。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong><code>[&quot;abc&quot;, &quot;bcd&quot;, &quot;acef&quot;, &quot;xyz&quot;, &quot;az&quot;, &quot;ba&quot;, &quot;a&quot;, &quot;z&quot;]</code>\n",
    "<strong>输出：</strong>\n",
    "[\n",
    "  [&quot;abc&quot;,&quot;bcd&quot;,&quot;xyz&quot;],\n",
    "  [&quot;az&quot;,&quot;ba&quot;],\n",
    "  [&quot;acef&quot;],\n",
    "  [&quot;a&quot;,&quot;z&quot;]\n",
    "]\n",
    "<strong>解释：</strong>可以认为字母表首尾相接，所以 &#39;z&#39; 的后续为 &#39;a&#39;，所以 [&quot;az&quot;,&quot;ba&quot;] 也满足 &ldquo;移位&rdquo; 操作规律。</pre>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [group-shifted-strings](https://leetcode.cn/problems/group-shifted-strings/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [group-shifted-strings](https://leetcode.cn/problems/group-shifted-strings/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"abc\",\"bcd\",\"acef\",\"xyz\",\"az\",\"ba\",\"a\",\"z\"]', '[\"a\"]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        def get_hash(string):\n",
    "            key = []\n",
    "            for a, b in zip(string, string[1:]):\n",
    "                key.append(chr((ord(b) - ord(a)) % 26 + ord(\"a\")))\n",
    "            return \"\".join(key)\n",
    "        groups = defaultdict(list)\n",
    "        for string in strings:\n",
    "            hash_key = get_hash(string)\n",
    "            print(hash_key)\n",
    "            groups[hash_key].append(string)\n",
    "        return list(groups.values())\n",
    "        # samelen_strings = defaultdict(list)\n",
    "        # for i in strings:\n",
    "        #     if len(i) == 1:\n",
    "        #         diff = 0\n",
    "        #         samelen_strings[(len(i), diff)].append(i)\n",
    "        #     elif len(i) == 2:\n",
    "        #         diff = ord(i[1]) - ord(i[0])\n",
    "        #         if diff < 0:\n",
    "        #             diff += 26\n",
    "        #         samelen_strings[(len(i), diff)].append(i)\n",
    "        #     else:\n",
    "        #         diff = ord(i[1]) - ord(i[0])\n",
    "        #         same_len = True\n",
    "        #         for j in range(2, len(i)):\n",
    "        #             temp = ord(i[j]) - ord(i[j - 1])\n",
    "                    \n",
    "        #             if temp < 0:\n",
    "        #                 temp += 26\n",
    "        #             if diff != temp:\n",
    "        #                 same_len = False\n",
    "        #                 break\n",
    "        #         if same_len == True:\n",
    "        #             samelen_strings[(len(i), diff)].append(i)\n",
    "        #         else:\n",
    "        #             samelen_strings[(-1, -1)].append(i)\n",
    "\n",
    "        # ans = []\n",
    "        \n",
    "        # for i in samelen_strings.keys():\n",
    "        #     if i != (-1, -1):\n",
    "        #         ans.append(samelen_strings[i])\n",
    "        #     else:\n",
    "               \n",
    "        #         for j in samelen_strings[i]:\n",
    "               \n",
    "        #             ans.append([j])\n",
    "\n",
    "\n",
    "        # return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def word_to_number(self, word):\n",
    "        res = ''\n",
    "        if len(word) == 1:\n",
    "            return ''\n",
    "        for i in range(len(word) - 1):\n",
    "            num = (ord(word[i + 1]) - ord(word[i]))%26\n",
    "            res += ',' + str(num)\n",
    "        return res\n",
    "\n",
    "    def groupStrings(self, strings: list[str]) -> list[list[str]]:\n",
    "        group_dict = defaultdict(list)\n",
    "        for word in strings:\n",
    "            group_dict[self.word_to_number(word)].append(word)\n",
    "        return list(group_dict.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        check_dic = defaultdict(list)\n",
    "        for word in strings:\n",
    "            k = ''\n",
    "            for i in range(len(word) - 1):\n",
    "                res = (ord(word[i + 1]) - ord(word[i])) % 26\n",
    "                k += 'h' + str(res)\n",
    "            check_dic[k].append(word)\n",
    "        return list(check_dic.values())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        mp = defaultdict(list)\n",
    "        for s in strings:\n",
    "            k = []\n",
    "            for c in s:\n",
    "                k.append((ord(c) - ord(s[0])) % 26)\n",
    "            mp[tuple(k)].append(s)\n",
    "        return list(mp.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        dic = defaultdict(list)\n",
    "\n",
    "        for s in strings:\n",
    "            key = []\n",
    "            start = s[0]\n",
    "            for i in range(1, len(s)):\n",
    "                key.append((ord(s[i]) - ord(start)) % 26)\n",
    "            str_key = \"#\".join(map(str, key))\n",
    "            dic[str_key].append(s)\n",
    "        \n",
    "        return [val for val in dic.values()]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        mp = {}\n",
    "        def tup(s: str) -> Optional[Tuple]:\n",
    "            lst = [ord(h)-ord(q)  if ord(h)-ord(q)>0 else ord(h)-ord(q)+26 for q,h in zip(s[:-1],s[1:])]\n",
    "            res,cnt = 0,26\n",
    "            for item in lst:\n",
    "                res+=item*cnt\n",
    "                cnt*=26\n",
    "            return res\n",
    "        res = []\n",
    "        for s in strings:\n",
    "            has = tup(s)\n",
    "            if has not in mp:\n",
    "                mp[has] = len(res)\n",
    "                res.append([s])\n",
    "            else:\n",
    "                res[mp[has]].append(s)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        d = defaultdict(list)\n",
    "        for s in strings:\n",
    "            root = ''.join([chr((ord(c) - ord(s[0]) + 26) % 26 + ord('a')) for c in s])\n",
    "            d[root].append(s)\n",
    "        return list(d.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        stringMapping = {}\n",
    "\n",
    "        for string in strings:\n",
    "            offset = []\n",
    "            for letter in string:\n",
    "                curOffset = ord(letter) - ord(string[0])\n",
    "                if curOffset < 0:\n",
    "                    curOffset += 26\n",
    "                offset.append(curOffset)\n",
    "            offset = tuple(offset)\n",
    "            if offset in stringMapping:\n",
    "                stringMapping[offset].append(string)\n",
    "            else:\n",
    "                stringMapping[offset] = [string]\n",
    "        \n",
    "        \n",
    "        return list(stringMapping.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        d =defaultdict(list)\n",
    "        for s in strings:\n",
    "            #  将 移位后相等的字符串 通过一种方式得到\n",
    "    \n",
    "            if s[0] == 'a':\n",
    "                d[s].append(s)\n",
    "            else:    \n",
    "                tmp = list(s)                       \n",
    "                for i in range(len(s)):\n",
    "                    # 对于每个单词，例如abc,转换成 012, 即 word-word[0] 对于每个字母。 然后把012放入字典，后面查找就行\n",
    "                    tmp[i] = chr( (ord(tmp[i]) - ord(s[0]) + 26) % 26 + ord('a') )\n",
    "                tmp = ''.join(tmp)\n",
    "                d[tmp].append(s)\n",
    "        return [v for i ,v in d.items()]\n",
    "     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        check = collections.defaultdict(list)\n",
    "\n",
    "        len1 = []\n",
    "        for s0 in strings:\n",
    "            if len(s0)==1:\n",
    "                len1.append(s0)\n",
    "                continue\n",
    "            found = False\n",
    "            for key in check:\n",
    "                if len(key)!=len(s0):\n",
    "                    continue \n",
    "                equal = True\n",
    "                for i in range(1,len(s0)):\n",
    "                    if (ord(s0[i])-ord(key[i]))%26 !=(ord(s0[i-1])-ord(key[i-1]))%26:\n",
    "                        equal = False\n",
    "                        break\n",
    "                if equal:\n",
    "                    check[key].append(s0)\n",
    "                    found = True\n",
    "                    break\n",
    "            if not found:\n",
    "                check[s0] = []\n",
    "        \n",
    "        ans = []\n",
    "        if len1:\n",
    "            ans.append(len1)\n",
    "        for key in check:\n",
    "            ans.append([key]+check[key])\n",
    "        return ans \n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        def hashCounter(s) -> str:\n",
    "            k = \"\"\n",
    "            offset = ord(s[0]) - ord(\"a\")\n",
    "            for c in s:\n",
    "                k += chr(ord(\"a\") + (ord(c) - ord(\"a\") - offset) % 26)\n",
    "            return k\n",
    "\n",
    "        ans = defaultdict(list)\n",
    "        for s in strings:\n",
    "            ans[hashCounter(s)].append(s)\n",
    "        return list(ans.values())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        def getGroup(string):\n",
    "            array = []\n",
    "            length = len(string)\n",
    "            for i in range(1,length):\n",
    "                diff = ord(string[i])-ord(string[i-1])\n",
    "                if diff < 0:\n",
    "                    diff += 26\n",
    "                array.append(diff)\n",
    "            return str(array)\n",
    "        groupMap = collections.defaultdict(list)\n",
    "        for s in strings:\n",
    "            group = getGroup(s)\n",
    "            groupMap[group].append(s)\n",
    "        return list(groupMap.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        dic = defaultdict(list)\n",
    "\n",
    "        def order(x):\n",
    "            if x < 0:\n",
    "                return x + 26\n",
    "            return x\n",
    "\n",
    "        for s in strings:\n",
    "            l = len(s)\n",
    "            d = [str(order(ord(s[i]) - ord(s[i+1]))) for i in range(l-1)]\n",
    "            key = str(l) + str('|') + ''.join(d)\n",
    "            dic[key].append(s)\n",
    "\n",
    "        return [dic[x] for x in dic]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        d = defaultdict(list)\n",
    "        for w in strings:\n",
    "            t = '0'\n",
    "            for i in range(1,len(w)):\n",
    "                ti = ord(w[i])\n",
    "                if w[i]<w[0]:\n",
    "                    t += f',{ti-ord(w[0])+26}'\n",
    "                else:\n",
    "                    t += f',{ti-ord(w[0])}'\n",
    "            d[t].append(w)\n",
    "        return list(d.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        def key_helper(string):\n",
    "            povit=string[0]\n",
    "            key=''\n",
    "            for char in string:\n",
    "                key+=str((ord(char)-ord(povit))%26)\n",
    "                key+=\" \"\n",
    "            return key\n",
    "        \n",
    "        hash_dict={}\n",
    "\n",
    "        for item in strings:\n",
    "            hash_key=key_helper(item)\n",
    "\n",
    "            if hash_key not in hash_dict:\n",
    "                hash_dict[hash_key]=[]\n",
    "            hash_dict[hash_key].append(item)\n",
    "        \n",
    "        res=[]\n",
    "\n",
    "        for key,val in hash_dict.items():\n",
    "            res.append(val)\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        counter = collections.defaultdict(list)\n",
    "        for s in strings:\n",
    "            temp = list(s)\n",
    "            temp = [str((ord(i)- ord(temp[0])) % 26) for i in temp]\n",
    "            temp = '*'.join(temp)\n",
    "            counter[temp].append(s)\n",
    "        return list(counter.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        hashmap={}\n",
    "        for i in strings:\n",
    "            lis=[]\n",
    "            for j in i:\n",
    "                change=chr(ord('a')+(ord(j)-ord(i[0])+26)%26)\n",
    "                lis.append(change)\n",
    "            str_change=''.join(lis)\n",
    "            hashmap[str_change]=hashmap.get(str_change,[])\n",
    "            hashmap[str_change].append(i)\n",
    "        return list(hashmap.values())\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        d =defaultdict(list)\n",
    "        for s in strings:\n",
    "            # s_ = \"\".join(sorted(i))  # 将 移位后相等的字符串 通过一种方式得到\n",
    "            \n",
    "            if s[0] == 'a':\n",
    "                d[s].append(s)\n",
    "            else:    \n",
    "                tmp = list(s)                       #转化成一种模式 从'a****'\n",
    "                for i in range(len(s)):\n",
    "                    tmp[i] = chr( (ord(tmp[i]) - ord(s[0]) + 26) % 26 + ord('a') )\n",
    "                tmp = ''.join(tmp)\n",
    "                d[tmp].append(s)\n",
    "\n",
    "         \n",
    "        return [v for i ,v in d.items()]\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        def hashSeq(s: str) -> int:\n",
    "            hs = ''\n",
    "            for i in range(1, len(s)):\n",
    "                diff = (ord(s[i]) - ord(s[i-1]) + 26) % 26\n",
    "                if diff < 10:  \n",
    "                    hs += \"0\" + str(diff)  \n",
    "                else:\n",
    "                    hs += str(diff)\n",
    "            return hs\n",
    "\n",
    "        arr = dict()\n",
    "        for s in strings:\n",
    "            hash = hashSeq(s)\n",
    "            li = arr.get(hash, list())\n",
    "            li.append(s)\n",
    "            arr[hash] = li\n",
    "\n",
    "        return list(arr.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        def hash(word):\n",
    "            # 相当于把所有单词还原到以a打头再重新算\n",
    "            ret = 0\n",
    "            base = ord(word[0]) - ord('a')\n",
    "            for c in word:\n",
    "                ret = ret * 26 + (ord(c) - base + 26) % 26\n",
    "            return ret\n",
    "\n",
    "        d = collections.defaultdict(list)\n",
    "        for word in strings:\n",
    "            d[hash(word)].append(word)\n",
    "        return list(d.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        # maxlen = max([len(s) for s in strings])\n",
    "        # strings_new = [[s for s in strings if len(s) == i] for i in range(1, maxlen+1)]\n",
    "        # r = []\n",
    "        # # print()\n",
    "        # for s in strings_new:\n",
    "        #     # print(len(s),s)\n",
    "        #     if len(s[0]) == 1 or len(s) == 1:\n",
    "        #         r.append(s)\n",
    "        # return r\n",
    "        #有思路但没实现\n",
    "        mp = defaultdict(list)\n",
    "        for s in strings:\n",
    "            if s[0] == 'a':\n",
    "                mp[s].append(s)\n",
    "            else:\n",
    "                key =list(s)\n",
    "                # print(key)\n",
    "                for i in range(len(s)):\n",
    "                    key[i] = chr((ord(key[i]) - ord(s[0]) + 26) % 26 + ord('a')) #########\n",
    "                key =''.join(key)\n",
    "                # print(key)\n",
    "                mp[key].append(s)\n",
    "        \n",
    "        res = []\n",
    "        for mode, sublist in mp.items():\n",
    "            res.append(sublist)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        def shift(s: str) -> str:\n",
    "            if s[0] == 'a':\n",
    "                return s\n",
    "            distance = ord(s[0])-ord('a')\n",
    "            ans = ''\n",
    "            for ch in s:\n",
    "                code = ord(ch) - distance\n",
    "                if code >= ord('a') and code <= ord('z'):\n",
    "                    ans += chr(code)\n",
    "                elif code < ord('a'):\n",
    "                    ans += chr(code+26)\n",
    "            return ans\n",
    "        # print(shift('ba'))\n",
    "        # print(shift('bcd'))\n",
    "        \n",
    "        dic=dict()\n",
    "        for s in strings:\n",
    "            shifted = shift(s)\n",
    "            if shifted not in dic:\n",
    "                dic[shifted] = [s]\n",
    "            else:\n",
    "                dic[shifted].append(s)\n",
    "        ans = []\n",
    "        for v in dic.values():\n",
    "            ans.append(v)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        def get_diff(s):\n",
    "            diff = []\n",
    "            for i in range(1, len(s)):\n",
    "                d = ord(s[i]) - ord(s[i-1])\n",
    "                if d < 0:\n",
    "                    d += 26\n",
    "                diff.append(d)\n",
    "            return tuple(diff)\n",
    "        \n",
    "        res = defaultdict(list)\n",
    "        for s in strings:\n",
    "            d = get_diff(s)\n",
    "            res[d].append(s)\n",
    "        return [res[x] for x in res]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        def hash(word):\n",
    "            ret = 0\n",
    "            base = ord(word[0]) - ord('a') - 26\n",
    "            for c in word:\n",
    "                ret = ret * 26 + (ord(c) - base) % 26\n",
    "            return ret\n",
    "\n",
    "        d = collections.defaultdict(list)\n",
    "        for word in strings:\n",
    "            d[hash(word)].append(word)\n",
    "        return list(d.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        record = collections.defaultdict(list)\n",
    "        mark = collections.defaultdict(list)\n",
    "        for word in strings:\n",
    "            record[len(word)].append(word)\n",
    "        res = []\n",
    "        dp = collections.defaultdict(int)\n",
    "        for i in range(26):\n",
    "            dp[chr(i+ord('a'))] = i\n",
    "        for length in record:\n",
    "            array = record[length]\n",
    "            if len(array) == 1 or length == 1:\n",
    "                res.append(array)\n",
    "            else:\n",
    "                for i in range(len(array)):\n",
    "                    c = array[i]\n",
    "                    mark[tuple([(dp[c[i]]+26-dp[c[i-1]])%26 for i in range(1, length)])].append(c)\n",
    "        # print(mark)\n",
    "        for key in mark:\n",
    "            res.append(mark[key])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "\n",
    "        def str_to_idx(s):\n",
    "            ret = []\n",
    "            base = ord(s[0])\n",
    "            for c in s:\n",
    "                ret.append((ord(c)-base)%26)\n",
    "            return tuple(ret)\n",
    "\n",
    "        groups = {}\n",
    "        for s in strings:\n",
    "            k = str_to_idx(s)\n",
    "            if not k in groups:\n",
    "                groups[k] = []\n",
    "            groups[k].append(s)\n",
    "        return list(groups.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        def genTuple(s):\n",
    "            cur = ord(s[0])\n",
    "            res = [0]\n",
    "            for l in s[1:]:\n",
    "                res.append((ord(l)-cur) % 26)\n",
    "            return tuple(res)\n",
    "        dic = dict()\n",
    "        for s in strings:\n",
    "            t = genTuple(s)\n",
    "            if t in dic:\n",
    "                dic[t].append(s)\n",
    "            else:\n",
    "                dic[t] = [s]\n",
    "        return [v for v in dic.values()]\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        def change_to_dis(word):\n",
    "            ans=[]\n",
    "            for i in range(len(word)-1):\n",
    "                ans.append((ord(word[i])-ord(word[i+1])+26)%26)\n",
    "            return ans\n",
    "        s=strings.copy()\n",
    "        for i in range(len(strings)):\n",
    "            strings[i]=[change_to_dis(strings[i]),i]\n",
    "        strings=sorted(strings,key=lambda x:x[0])\n",
    "        i=0\n",
    "        ret=[]\n",
    "        while i<len(strings):\n",
    "            ans=[]\n",
    "            ans.append(s[strings[i][1]])\n",
    "            i+=1\n",
    "            if i<len(strings):\n",
    "                while strings[i-1][0]==strings[i][0]:\n",
    "                    ans.append(s[strings[i][1]])\n",
    "                    i+=1\n",
    "                    if i==len(strings):\n",
    "                        break\n",
    "            \n",
    "            ret.append(ans)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        dic = collections.defaultdict(list)\n",
    "        res = []\n",
    "\n",
    "        for s in strings:\n",
    "            val = 0\n",
    "            base = 1\n",
    "            for c in s:\n",
    "                diff = ord(c) - ord(s[0])\n",
    "                if diff <= 0:\n",
    "                    diff = 26 + diff\n",
    "                val += diff * base\n",
    "                base *= 10\n",
    "            dic[val].append(s)\n",
    "        print(dic)\n",
    "        return list(dic.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def word_to_number(self, word):\n",
    "        if len(word)==1:\n",
    "            return ''\n",
    "\n",
    "        res = ''\n",
    "        for i in range(len(word)-1):\n",
    "            num = (ord(word[i+1])-ord(word[i]))%26\n",
    "            res += ' '+str(num)\n",
    "        return res\n",
    "\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        g_dict = defaultdict(list)\n",
    "        for word in strings:\n",
    "            g_dict[self.word_to_number(word)].append(word)\n",
    "\n",
    "        return list(g_dict.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        dic = defaultdict(list)\n",
    "\n",
    "        def order(x):\n",
    "            if x < 0:\n",
    "                return x + 26\n",
    "            return x\n",
    "\n",
    "        for s in strings:\n",
    "            l = len(s)\n",
    "            d = [str(order(ord(s[i]) - ord(s[i+1]))) for i in range(l-1)]\n",
    "            key = str(l) + str('|') + ''.join(d)\n",
    "            dic[key].append(s)\n",
    "\n",
    "        return [dic[x] for x in dic]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        def hashCounter(string):\n",
    "            return tuple(((ord(string[i])-ord(string[i-1]))%26) for i in range(1,len(string))) if len(string)>1 else 0\n",
    "        ans=defaultdict(list)\n",
    "        for s in strings:\n",
    "            ans[hashCounter(s)].append(s)\n",
    "        return list(ans.values())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        d = collections.defaultdict(list)\n",
    "        for s in strings:\n",
    "            key = []\n",
    "            for i, ch in enumerate(s):\n",
    "                if i > 0:\n",
    "                    key.append((ord(s[i]) - ord(s[i-1]) + 26)%26)\n",
    "            d[tuple(key)].append(s)\n",
    "        return list(d.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        res = {}\n",
    "        for string in strings:\n",
    "            idx = [ord(i) for i in string]\n",
    "            mark = idx[0]\n",
    "            idx = [i-mark for i in idx]\n",
    "            idx = [str(i+26) if i < 0 else str(i) for i in idx]\n",
    "            idx = \" \".join(idx)\n",
    "            if idx not in res:\n",
    "                res[idx] = [string]\n",
    "            else:\n",
    "                res[idx].append(string)\n",
    "        return list(res.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        mp = defaultdict(list)\n",
    "        for s in strings :\n",
    "            if s[0] == 'a':\n",
    "                mp[s].append(s)\n",
    "            else:\n",
    "                key = list(s)\n",
    "                for i in range(len(s)):\n",
    "                    key[i] = chr( (ord(key[i]) - ord(s[0]) + 26) % 26 + ord('a') )\n",
    "                key = ''.join(key)\n",
    "                mp[key].append(s)\n",
    "\n",
    "        res = []\n",
    "        for mode, sublist in mp.items():\n",
    "            res.append(sublist)         \n",
    "\n",
    "        return  res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        def check(s):\n",
    "            ans = []\n",
    "            for i in s:\n",
    "                ans.append(str((ord(i)-ord(s[0])) % 26))\n",
    "            return str(ans)\n",
    "        from collections import defaultdict\n",
    "        index = defaultdict(list)\n",
    "        for i in strings:\n",
    "            index[check(i)].append(i)\n",
    "        return list(index.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        def check(s):\n",
    "            base = ord(s[0])\n",
    "            return tuple((base-ord(i)) % 26 for i in s)\n",
    "\n",
    "        from collections import defaultdict\n",
    "        index = defaultdict(list)\n",
    "        for i in strings:\n",
    "            index[check(i)].append(i)\n",
    "        return list(index.values())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        ret = collections.defaultdict(list)\n",
    "        for s in strings:\n",
    "            diffs = []\n",
    "            for i in range(1, len(s)):\n",
    "                if s[i] > s[i - 1]:\n",
    "                    diff = ord(s[i]) - ord(s[i - 1])\n",
    "                else:\n",
    "                    diff = ord(s[i]) - ord(\"a\") + 1 + ord(\"z\") - ord(s[i - 1])\n",
    "                diffs.append(diff)\n",
    "            ret[tuple(diffs)].append(s)\n",
    "       \n",
    "        return [ret[k] for k in ret]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        dic = collections.defaultdict(list)\n",
    "        for word in strings:\n",
    "            # tmp = [0] * 26 # wrong!!!!!\n",
    "            tmp = []\n",
    "            for ch in word:\n",
    "                val = (ord(ch) - ord(word[0])) % 26 # -1%26=25\n",
    "                tmp.append(val)\n",
    "                # tmp[index] += 1 wrong\n",
    "            dic[tuple(tmp)].append(word) # [] not ()\n",
    "        return list(dic.values())\n",
    "\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        result=defaultdict(list)\n",
    "        for x in strings:\n",
    "            if len(x)<=1:\n",
    "                result[(0)].append(x)\n",
    "            else:\n",
    "                key=[]\n",
    "                for i in range(1,len(x)):\n",
    "                    key.append((ord(x[i])-ord(x[i-1]))%26)\n",
    "                # print(key)\n",
    "                result[tuple(key)].append(x)\n",
    "        return list(result.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]] :\n",
    "        mp = defaultdict(list)\n",
    "        for s in strings:\n",
    "            if s[0] == 'a':\n",
    "                mp[s].append(s)\n",
    "            else:\n",
    "                key = list(s)\n",
    "                for i, ch in enumerate(key):\n",
    "                    key[i] = chr((ord(key[i]) - ord(s[0]) + 26 ) % 26 + ord('a'))\n",
    "                key = \"\".join(key)\n",
    "                mp[key].append(s)\n",
    "\n",
    "        res = []\n",
    "        for key, value in mp.items():\n",
    "            res.append(value)\n",
    "\n",
    "        return  res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        c=defaultdict(list)\n",
    "        def get(word):\n",
    "            t=0\n",
    "            k=ord(word[0])-ord('a')\n",
    "            for w in word:\n",
    "                ws=ord(w)-ord('a')-k\n",
    "                if ws<0:ws+=26\n",
    "                t*=27\n",
    "                t+=ws+1\n",
    "            return t\n",
    "        for w in strings:\n",
    "            c[get(w)].append(w)\n",
    "        return list(c.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        dic = collections.defaultdict(list) # hash: list\n",
    "        n = len(strings)\n",
    "        base = 1\n",
    "\n",
    "        for s in strings:\n",
    "            base = 1\n",
    "            hs = 0 \n",
    "            for c in s:\n",
    "                diff = ord(c) - ord(s[0])\n",
    "                if diff <= 0:\n",
    "                    diff += 26\n",
    "                hs = hs + diff * base\n",
    "                base *= 10\n",
    "            dic[hs].append(s)\n",
    "        \n",
    "        return list(dic.values())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        dic = collections.defaultdict(list)\n",
    "\n",
    "        for s in strings:\n",
    "            base = 1\n",
    "            hashVal = 0\n",
    "            for i in range(len(s)):\n",
    "                diff = ord(s[i]) - ord(s[0])\n",
    "                if diff <= 0: # ==的情况不能+0，因为这样的话a,aa就是同一个key了，所以这里+26\n",
    "                    hashVal += (26 + diff) * base\n",
    "                else:\n",
    "                    hashVal += diff * base\n",
    "                base *= 10\n",
    "            dic[hashVal].append(s)\n",
    "        # print(dic)\n",
    "        \n",
    "        return list(dic.values())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        \"\"\"\n",
    "        Hash table [(diff_tuple) -> group_strings]\n",
    "        \"\"\"\n",
    "\n",
    "        def compute_diff_tuple(s: str) -> tuple[int, ...]:\n",
    "            diffs = []\n",
    "\n",
    "            for index in range(len(s) - 1):\n",
    "                diff = (ord(s[index + 1]) - ord(s[index])) % 26\n",
    "                diffs.append(diff)\n",
    "\n",
    "            return tuple(diffs)\n",
    "\n",
    "        from collections import defaultdict\n",
    "        diff_tuple_to_group_strings = defaultdict(list)\n",
    "\n",
    "        for string in strings:\n",
    "            diff_tuple = compute_diff_tuple(string)\n",
    "            diff_tuple_to_group_strings[diff_tuple].append(string)\n",
    "\n",
    "        return list(diff_tuple_to_group_strings.values())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        dic = defaultdict(list)\n",
    "\n",
    "        def order(x):\n",
    "            if x < 0:\n",
    "                return x + 26\n",
    "            return x\n",
    "\n",
    "        for s in strings:\n",
    "            l = len(s)\n",
    "            d = [str(order(ord(s[i]) - ord(s[i+1]))) for i in range(l-1)]\n",
    "            key = str(l) + str('|') + ''.join(d)\n",
    "            dic[key].append(s)\n",
    "\n",
    "        return [dic[x] for x in dic]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        result=defaultdict(list)\n",
    "        for x in strings:\n",
    "            if len(x)<=1:\n",
    "                result[(0)].append(x)\n",
    "            else:\n",
    "                key=[]\n",
    "                for i in range(1,len(x)):\n",
    "                    key.append((ord(x[i])-ord(x[i-1]))%26)\n",
    "                # print(key)\n",
    "                result[tuple(key)].append(x)\n",
    "        return list(result.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        import collections\n",
    "        res = collections.defaultdict(list)\n",
    "        \n",
    "        def convert_to_relative(string):\n",
    "            if len(string) == 0:\n",
    "                return []\n",
    "            rela_distance = [0]\n",
    "            for i in range(1, len(string)):\n",
    "                if ord(string[i])-ord(string[i-1]) < 0:\n",
    "                    rela_distance.append(26+ord(string[i])-ord(string[i-1]))\n",
    "                else:\n",
    "                    rela_distance.append(ord(string[i])-ord(string[i-1]))\n",
    "            return \",\".join([str(x) for x in rela_distance])\n",
    "        \n",
    "        for string in strings:\n",
    "            rela_distance = convert_to_relative(string)\n",
    "            res[rela_distance].append(string)\n",
    "\n",
    "        return list(res.values())                                                                                          "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        def check(s):\n",
    "            return \"_\".join(str((ord(i) - ord(s[0])) % 26) for i in s)\n",
    "\n",
    "        from collections import defaultdict\n",
    "        index = defaultdict(list)\n",
    "        for i in strings:\n",
    "            index[check(i)].append(i)\n",
    "        return list(index.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        def getv(s):\n",
    "            t = s[0]\n",
    "            res = []\n",
    "            for ss in s:\n",
    "                v = ord(ss)-ord(t)\n",
    "                if v < 0:\n",
    "                    v += 26\n",
    "                res.append(v)\n",
    "                t = ss\n",
    "            return str(res)\n",
    "\n",
    "        hs = {}\n",
    "        for ss in strings:\n",
    "            k = getv(ss)\n",
    "            if k not in hs:\n",
    "                hs[k] = [ss]\n",
    "            else:\n",
    "                hs[k].append(ss)\n",
    "\n",
    "        res = []\n",
    "        for k,v in hs.items():\n",
    "            res.append(v)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        map1 = collections.defaultdict(list)\n",
    "        for s in strings:\n",
    "            temp = ()\n",
    "            for ch in s:\n",
    "                temp+=(ord(ch)- ord(s[0]))% 26, \n",
    "            map1[temp].append(s)\n",
    "        return list(map1.values())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        \n",
    "        def hash(org):\n",
    "            delta = ord(org[0]) - ord('a')\n",
    "            ret = \"\".join([chr(((ord(w) - delta) + 52) % 26) for w in org])\n",
    "            return ret\n",
    "\n",
    "        clips = defaultdict(list)\n",
    "\n",
    "        for s in strings:\n",
    "            clips[hash(s)].append(s)\n",
    "        return list(clips.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        def check(s):\n",
    "            base = ord(s[0])\n",
    "            return tuple((ord(i) - base) % 26 for i in s)\n",
    "\n",
    "        from collections import defaultdict\n",
    "        index = defaultdict(list)\n",
    "        for i in strings:\n",
    "            index[check(i)].append(i)\n",
    "        return list(index.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "\n",
    "        def hashCounter(s):\n",
    "            if len(s) <= 1:\n",
    "                return (0)\n",
    "            return tuple(\n",
    "                (ord(s[i]) - ord(s[i-1])) % 26\n",
    "                for i in range(1, len(s))\n",
    "            )\n",
    "        \n",
    "        ans = defaultdict(list)\n",
    "\n",
    "        for s in strings:\n",
    "            ans[hashCounter(s)].append(s)\n",
    "\n",
    "        return list(ans.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        dic = defaultdict(list)\n",
    "\n",
    "        def order(x):\n",
    "            if x < 0:\n",
    "                return x + 26\n",
    "            return x\n",
    "\n",
    "        for s in strings:\n",
    "            l = len(s)\n",
    "            d = [str(order(ord(s[i]) - ord(s[i+1]))) for i in range(l-1)]\n",
    "            key = str(l) + str('|') + ''.join(d)\n",
    "            dic[key].append(s)\n",
    "\n",
    "        return [dic[x] for x in dic]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        if strings == [\"\"]:\n",
    "            return [[\"\"]]\n",
    "        def hist(s):\n",
    "            re = []\n",
    "            for i in range(len(s)):\n",
    "                re.append( ord(s[i])-ord('a'))\n",
    "            first_value = re[0]\n",
    "            diff = first_value - 0\n",
    "            re = [(x - diff + 26) % 26 for x in re]\n",
    "            # min_value = min(re)\n",
    "            # re = [x - min_value for x in re]\n",
    "            # re = [x - 26 if x >= 13 else x for x in re]\n",
    "            # min_value = min(re)\n",
    "            # re = [x - min_value for x in re]\n",
    "            return tuple(re)\n",
    "        d = {}\n",
    "        for i in range(len(strings)):\n",
    "            m = hist(strings[i])\n",
    "            if m in d:\n",
    "                d[m].append(strings[i])\n",
    "            else:\n",
    "                d[m] = [strings[i]]\n",
    "        re = []\n",
    "        for k in d:\n",
    "            re.append(d[k])\n",
    "        # print(re)\n",
    "        return re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        hashmap = {}\n",
    "        for s in strings:\n",
    "            t = []\n",
    "            for c in s:\n",
    "                c = chr((ord(c) - ord(s[0]) + 26) % 26 + ord('a'))\n",
    "                t.append(c)\n",
    "            key = \"\".join(t)\n",
    "            values = hashmap.get(key, [])\n",
    "            values.append(s)\n",
    "            hashmap[key] = values\n",
    "        \n",
    "        res = []\n",
    "        for key, values in hashmap.items():\n",
    "            res.append(values)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        res = {}\n",
    "        for string in strings:\n",
    "            idx = [ord(i) for i in string]\n",
    "            mark = idx[0]\n",
    "            idx = [i-mark for i in idx]\n",
    "            idx = [str(i+26) if i < 0 else str(i) for i in idx]\n",
    "            idx = \" \".join(idx)\n",
    "            if idx not in res:\n",
    "                res[idx] = [string]\n",
    "            else:\n",
    "                res[idx].append(string)\n",
    "        return list(res.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        groups= defaultdict(list)\n",
    "\n",
    "        def hashStr(s):\n",
    "            l = len(s)\n",
    "            hs = [l]\n",
    "            for i in range(l-1):\n",
    "                hs.append((ord(s[i+1]) - ord(s[i]))%26)\n",
    "            return tuple(hs)\n",
    "        \n",
    "        for s in strings:\n",
    "            hs = hashStr(s)\n",
    "            groups[hs].append(s)\n",
    "        \n",
    "        return list(groups.values())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:  \n",
    "        \"\"\"\n",
    "        map里面存后一位和前一位的差值\n",
    "        {(1,1): ['abc', 'bcd', 'xyz'], \n",
    "        (2,2,1): ['acef'], \n",
    "        (2,5): ['az', 'ba'], \n",
    "        (0): ['a', 'z']}\n",
    "        \"\"\"\n",
    "        map = defaultdict(list)\n",
    "        for string in strings:\n",
    "            diff = []\n",
    "            for i in range(1, len(string)):\n",
    "                diff.append(((ord(string[i]) - ord(string[i-1])) % 26))\n",
    "            \n",
    "            diff = tuple(diff)\n",
    "            map[diff].append(string)\n",
    "\n",
    "        result = []\n",
    "        for k, v in map.items():\n",
    "            result.append(v)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        res = {}\n",
    "        for string in strings:\n",
    "            idx = [ord(i) for i in string]\n",
    "            mark = idx[0]\n",
    "            idx = [i-mark for i in idx]\n",
    "            idx = [str(ord(\"z\")+i+1-ord(\"a\")) if i < 0 else str(i) for i in idx]\n",
    "            idx = \" \".join(idx)\n",
    "            if idx not in res:\n",
    "                res[idx] = [string]\n",
    "            else:\n",
    "                res[idx].append(string)\n",
    "        return list(res.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        d = collections.defaultdict(list)\n",
    "        for s in strings:\n",
    "            key = []\n",
    "            for i, ch in enumerate(s):\n",
    "                if i > 0:\n",
    "                    key.append((ord(s[i]) - ord(s[i-1]) + 26)%26)\n",
    "            d[tuple(key)].append(s)\n",
    "        return list(d.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        def hash(string):\n",
    "            if len(string) == 0:\n",
    "                return tuple([0])\n",
    "            res = []\n",
    "            for i in range(len(string)-1):\n",
    "                res.append((ord(string[i+1])-ord(string[i]))%26)\n",
    "            return tuple(res)\n",
    "        \n",
    "        dic = {}\n",
    "        for s in strings:\n",
    "            if hash(s) not in dic:\n",
    "                dic[hash(s)] = [s]\n",
    "            else:\n",
    "                dic[hash(s)].append(s)\n",
    "        return list(dic.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        pattern_dict = defaultdict(list)\n",
    "        for s in strings:\n",
    "            pattern = self.converted(s)\n",
    "            pattern_dict[pattern].append(s)\n",
    "        return list(pattern_dict.values())\n",
    "    \n",
    "    def converted(self, s):\n",
    "        l = [0]\n",
    "        n = len(s)\n",
    "        for i in range(1, n):\n",
    "            l.append((ord(s[i]) - ord(s[i-1]) + 26) % 26)\n",
    "        return tuple(l)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        dis_arrs = collections.defaultdict(list)\n",
    "        for string in strings:\n",
    "            dis = []\n",
    "            i = 1\n",
    "            while i < len(string):\n",
    "                dis.append(str((ord(string[i]) - ord(string[i-1])) % 26))\n",
    "                i += 1\n",
    "            dis_arrs[\".\".join(dis)].append(string)\n",
    "        \n",
    "        return list(dis_arrs.values())\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        res = {}\n",
    "        for string in strings:\n",
    "            idx = [ord(i) for i in string]\n",
    "            mark = idx[0]\n",
    "            idx = [i-mark for i in idx]\n",
    "            idx = [str(ord(\"z\")+i+1-ord(\"a\")) if i < 0 else str(i) for i in idx]\n",
    "            idx = \" \".join(idx)\n",
    "            if idx not in res:\n",
    "                res[idx] = [string]\n",
    "            else:\n",
    "                res[idx].append(string)\n",
    "        print(res)\n",
    "        print(ord(\"a\"))\n",
    "        return list(res.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def word_to_number(self, word):\n",
    "        res = ''\n",
    "        if len(word) == 1:\n",
    "            return ''\n",
    "        for i in range(len(word) - 1):\n",
    "            num = (ord(word[i + 1]) - ord(word[i]))%26\n",
    "            res += ',' + str(num)\n",
    "        return res\n",
    "        ### key 是总结出来的字母之间的差值\n",
    "\n",
    "    def groupStrings(self, strings: list[str]) -> list[list[str]]:\n",
    "        group_dict = collections.defaultdict(list)\n",
    "        for word in strings:\n",
    "            group_dict[self.word_to_number(word)].append(word)\n",
    "        #print(group_dict)\n",
    "        return list(group_dict.values())\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        dt=dict()\n",
    "        def getK(s):\n",
    "            res=[]\n",
    "            for i in range(1,len(s)):\n",
    "                dx=ord(s[i])-ord(s[i-1])\n",
    "                if dx<0:dx+=26\n",
    "                res.append(dx)\n",
    "            return tuple(res)\n",
    "        for i in strings:\n",
    "            key=getK(i)\n",
    "            if key in dt:\n",
    "                dt[key].append(i)\n",
    "            else:\n",
    "                dt[key]=[i]\n",
    "        print(dt)\n",
    "        ans=[]\n",
    "        for (key,val) in dt.items():\n",
    "            ans.append(val)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        cnt = defaultdict(list)\n",
    "        res = []\n",
    "        j = 0\n",
    "        for s in strings:\n",
    "            if len(s) == 1:\n",
    "                if not res:\n",
    "                    res.append([s])\n",
    "                    cnt[j] = []\n",
    "                    j += 1\n",
    "                else:\n",
    "                    if [] not in cnt.values():\n",
    "                        cnt[j] = []\n",
    "                        j += 1\n",
    "                    for k in cnt:\n",
    "                        if cnt[k] == []:\n",
    "                            if k >= len(res):\n",
    "                                res.append([s])\n",
    "                            else:\n",
    "                                res[k].append(s)\n",
    "            else:\n",
    "                a = []\n",
    "                for i in range(1, len(s)):\n",
    "                    a.append((ord(s[i]) - ord(s[i - 1])) % 26)\n",
    "                if a in cnt.values():\n",
    "                    for k in cnt:\n",
    "                        if cnt[k] == a:\n",
    "                            res[k].append(s)\n",
    "                else:\n",
    "                    cnt[j] = a \n",
    "                    res.append([s])\n",
    "                    j += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        self.parents = list(range(len(strings)))\n",
    "        for i in range(len(strings)):\n",
    "            for j in range(i + 1, len(strings)):\n",
    "                if self.check(strings[i], strings[j]):\n",
    "                    root_a = self.get_root(i)\n",
    "                    root_b = self.get_root(j)\n",
    "                    self.parents[root_b] = root_a\n",
    "        print(self.parents)\n",
    "        ans = {}\n",
    "        for i in range(len(strings)):\n",
    "            if self.parents[i] not in ans:\n",
    "                ans[self.parents[i]] = []\n",
    "            ans[self.parents[i]].append(strings[i])\n",
    "        return [_ for _ in ans.values()]\n",
    "\n",
    "\n",
    "    def get_root(self, i):\n",
    "        if self.parents[i] != i:\n",
    "            self.parents[i] = self.get_root(self.parents[i])\n",
    "        return self.parents[i]\n",
    "\n",
    "    def check(self, a, b):\n",
    "        if len(a) != len(b):\n",
    "            return False\n",
    "        interval = (ord(a[0]) - ord(b[0])) % 26\n",
    "        # print(a, b, interval)\n",
    "        for i, j in zip(a[1:], b[1:]):\n",
    "            if (ord(i) - ord(j)) % 26 != interval:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        res = []\n",
    "        dic = collections.defaultdict(list)\n",
    "        for strs in strings:\n",
    "            tmp = []\n",
    "            start = strs[0]\n",
    "            for ch in strs:\n",
    "                x = ord(start) - ord(ch)\n",
    "                x = x % 26 # % 26!!!!\n",
    "                tmp.append(x)\n",
    "            dic[tuple(tmp)].append(strs)\n",
    "        return list(dic.values())\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        return self.answer_1(strings)\n",
    "\n",
    "    def answer_1(self, strings):\n",
    "        storage = collections.defaultdict(list)\n",
    "\n",
    "        for word in strings:\n",
    "            key = self._get_word_key(word)\n",
    "            storage[key].append(word)\n",
    "        return list(storage.values())\n",
    "\n",
    "    @classmethod\n",
    "    def _get_word_key(cls, word):\n",
    "        word_len = len(word)\n",
    "\n",
    "        if word_len == 1:\n",
    "            return \"\"\n",
    "\n",
    "        key = \"\"\n",
    "\n",
    "        for index in range(word_len - 1):\n",
    "            key_char = (ord(word[index + 1]) - ord(word[index]) + 26) % 26\n",
    "            key += str(key_char) + \",\"\n",
    "        return key"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def word_to_number(self, word):\n",
    "        res = ''\n",
    "        if len(word) == 1:\n",
    "            return ''\n",
    "        for i in range(len(word) - 1):\n",
    "            num = (ord(word[i + 1]) - ord(word[i]))%26\n",
    "            res += ',' + str(num)\n",
    "        return res\n",
    "\n",
    "    def groupStrings(self, strings: list[str]) -> list[list[str]]:\n",
    "        group_dict = defaultdict(list)\n",
    "        for word in strings:\n",
    "            group_dict[self.word_to_number(word)].append(word)\n",
    "        return list(group_dict.values())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def groupStrings(self, strings: List[str]) -> List[List[str]]:\n",
    "        hashmap = {}\n",
    "        for word in strings:\n",
    "            key = []\n",
    "            for char in word:\n",
    "                print(char)\n",
    "                shifted_char = chr((ord(char) - ord(word[0]) + 26) % 26 + ord('a'))\n",
    "                print(shifted_char)\n",
    "                print()\n",
    "                key.append(shifted_char)\n",
    "            key_str = ''.join(key)\n",
    "            # if key_str not in hashmap:\n",
    "            #     hashmap[key_str] = []\n",
    "            \n",
    "            # hashmap[key_str].append(word)\n",
    "            hashmap[key_str]=hashmap.get(key_str,[])\n",
    "            hashmap[key_str].append(word)\n",
    "        return list(hashmap.values())"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
